package com.example.lcode.backtrack;

import java.util.ArrayList;
import java.util.List;

public class Question95 {

    public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
    }

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int left, int right) {
        List<TreeNode> res = new ArrayList<>();
        if (left > right) {
            res.add(null);
            return res;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftNodes = generateTrees(left, i - 1);
            List<TreeNode> rightNodes = generateTrees(i + 1, right);
            for (int j = 0; j < leftNodes.size(); j++) {
                for (int k = 0; k < rightNodes.size(); k++) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftNodes.get(j);
                    treeNode.right = rightNodes.get(k);
                    res.add(treeNode);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {

    }

}
